﻿#include <stdio.h>

//给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
//head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]
//head = [], val = 1 输出：[]
//head = [7,7,7,7], val = 7 输出：[]
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* removeElements(struct ListNode* head, int val)
{
    struct ListNode* cur = NULL,*phead = head;
    if(head == NULL)
        return NULL;

    while(phead)
    {
        if(phead->val == val)
        {
            if(head->val == val)
            {
                head = phead->next;
                free(phead);
                phead = head;
            }
            else
            {
                cur->next = phead->next;
                free(phead);
                phead = cur->next;
            }   
        }
        else
        {
            cur = phead;
            phead = phead->next;
        }
    }
    return head;
}


//*******************************************************************************************************************************************************************
//给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* newhead = NULL,*cur = head,*tail = NULL;

    while(cur)
    {
        newhead = cur;
        cur = cur->next;

        newhead->next = tail;
        tail = newhead;

    }
    return newhead;
}

//*******************************************************************************************************************************************************************
/*
给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

 

示例 1：

输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
示例 2：

输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/middle-of-the-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* slow = head,*faast = head;
    if(head == NULL)
        return  head;
    while(faast != NULL && faast->next != NULL)
    {
        faast = faast->next->next;
        slow = slow->next;
    }
    return slow;
}

//*******************************************************************************************************************************************************************

/*输入一个链表，输出该链表中倒数第k个结点。
示例1
输入：
1,{1,2,3,4,5}
复制
返回值：
{5}*/

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

/**
 * 
 * @param pListHead ListNode类 
 * @param k int整型 
 * @return ListNode类
 */
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) 
{
    // write code here
    struct ListNode* fast = pListHead,*slow = pListHead;

    while(k--)
    {
        if(fast == NULL)
            return NULL;
        fast = fast->next;
    }

    while(fast)
    {
        
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}
//*******************************************************************************************************************************************************************
/*
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

 

示例 1：


输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：

输入：l1 = [], l2 = []
输出：[]
示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/merge-two-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
//
    struct ListNode* L1 = list1,*L2 = list2,*newhead = NULL,*cur = NULL;
    newhead = (struct ListNode*)malloc(sizeof(struct ListNode));
    cur = newhead;

    while(L1 && L2)
    {
        if(L1->val > L2->val)
        {
            cur->next = L2;
            cur = cur->next;
            L2 = L2->next;
        }
        else
        {
            cur->next = L1;
            cur = cur->next;
            L1 = L1->next;
        }
    }
    if(L2 == NULL)
    {
        cur->next = L1;
    }
    else
    {
        cur->next = L2;
    }
    return newhead->next;
}
//*******************************************************************************************************************************************************************
/*
现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

 1243124  3
 1212344

*/





/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) 
    {
        // write code here
        ListNode*  LittleHead,*BigHead,*big,*little,*cur;
        cur = pHead;
        LittleHead = (ListNode*)malloc(sizeof(struct ListNode));
        little = LittleHead;
        BigHead = (ListNode*)malloc(sizeof(struct ListNode));
        big = BigHead;

        while(cur)
        {
            if(cur->val < x)
            {
                little->next = cur;
                little = cur;
                cur = cur->next;
            }
            else
            {
                big->next = cur;
                big = cur;
                cur = cur->next;               
            }
        }
        little->next = BigHead->next;
        big->next = NULL;
        ListNode* newhead = LittleHead->next;
        free(LittleHead);
        free(BigHead);
        return newhead;
    }
};

//*******************************************************************************************************************************************************************
/*
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

测试样例：
1->2->2->1
返回：true
*/

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A)
    {
        // write code here
        
        //1.找到中间节点
        ListNode* slow = A,*fast = A;

        while(fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
		//方法1
        //2.分别把val加在一起比较
        fast = A;
        int A1 = 0,A2 = 0;
        while(fast != slow)
        {
            A1 = A1+fast->val;
            fast = fast->next;
        }
        while(slow)
        {
            A2 = A2+slow->val;
            slow = slow->next;
        }
        
        if(A1 == A2)
            return true;
        else
           return false;




		/*    方法 2   
		//2.逆置后半个
         ListNode* tail = NULL,*head = NULL;
        while(slow)
        {
            head = slow;
            slow = slow->next;
            head->next = tail;
            tail = head;
        }
        //3.比较val 不相等则退出
        slow = head;
        fast = A;
        while(slow)
        {
            if(slow->val != fast->val)
                return false;
            
            slow = slow->next;
            fast = fast->next;
        }
        return true;
		*/

    }
};

//*******************************************************************************************************************************************************************
/*
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：



题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
listA - 第一个链表
listB - 第二个链表
skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/intersection-of-two-linked-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/



/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    struct ListNode * Acur = headA,*Bcur = headB;
    int countA = 1,countB = 1;
    while(Acur->next)
    {
        Acur = Acur->next;
        countA++;
    }
    while(Bcur->next)
    {
        Bcur = Bcur->next;
        countB++;
    }
    if(Acur != Bcur)
        return NULL;

    Acur = headA;
    Bcur = headB;
    Acur = countA > countB? Acur:Bcur;
    if(Acur == Bcur)
        Bcur = headA;
    countA = abs(countA-countB);

    while(countA--)
        Acur = Acur->next;

    while(Acur != Bcur)
    {
        Acur = Acur->next;
        Bcur = Bcur->next;
    }
    return Acur;
}

//*******************************************************************************************************************************************************************
/*
给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/linked-list-cycle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/




/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) 
{
        struct ListNode * slow = head,*fast = head;

        while(fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
            if(slow == fast)
                return 1;
        }   
    return false;
        
}
//*******************************************************************************************************************************************************************
/*
给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/linked-list-cycle-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/



/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head) 
{
    struct ListNode* slow = head,*fast = head;

    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(slow == fast)
            break;
    }
    if(fast == NULL || fast->next == NULL)
        return NULL;
    slow = head;
    while(slow != fast)
    {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}



//*******************************************************************************************************************************************************************
/*
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为  null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/copy-list-with-random-pointer
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/


/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */

struct Node* init(int x)
{
    struct Node* new = (struct Node*)malloc(sizeof(struct Node));
        if(new == NULL)
        {
            perror("malloc");
            exit(-1);
        }
        new->val = x;
        new->next = NULL;
        return new;
}

struct Node* copyRandomList(struct Node* head) 
{
	struct Node* cur = head;
    while(cur)
    {   
        struct Node*new = init(cur->val);      
        new->next = cur->next;
        cur->next = new;
        cur = new->next; 
    }
    cur = head;
    struct Node* Next  = NULL;
    while(cur)
    {   
        Next = cur->next;
        if(cur->random == NULL)
            Next->random = NULL;
        else
            Next->random = cur->random->next;
        cur = Next->next;
    }
    struct Node* copyHead = NULL,*copyCur = NULL;
    cur = head;  
    while(cur)
    {
        Next = cur->next;
        if(copyHead == NULL)
        {
            copyHead =  Next;
            copyCur = copyHead;
        }
        else
        {
            copyCur->next = Next;
            copyCur = Next;
        }
        cur->next = Next->next;
        cur = Next->next;
    }
    return copyHead;
}